package com.lijing.avlTree;

import com.sun.org.apache.bcel.internal.generic.NEW;

/**
 * @Description 节点
 * @title: Node
 * @Author LiJing
 * @Date: 2021/3/2910:40 下午
 * @Version 1.0
 */
public class Node {
    private int value;
    private Node left;
    private Node right;

    /**
     * add a Node
     * @param node the node to be added
     */
    public void add(Node node){
        if (node == null){
            return;
        }else if (node.getValue() < this.getValue()){
            if (this.getLeft() == null){
                this.setLeft(node);
            }else {
                this.getLeft().add(node);
            }
        }else {
            if (this.getRight() == null){
                this.setRight(node);
            }else {
                this.getRight().add(node);
            }
        }

        if (this.rightHeight() - this.leftHeight() > 1){
            if (this.getRight() != null && this.getRight().leftHeight() > this.getRight().rightHeight()){
                this.getRight().rightRotate();
                leftRotate();
            }else {
                leftRotate();
            }
            return;
        }
        if (this.leftHeight() - this.rightHeight() > 1){
            if (this.getLeft() != null && this.getLeft().rightHeight() > this.getLeft().leftHeight()){
                this.getLeft().leftRotate();
                rightRotate();
            }else {
                rightRotate();
            }
            return;
        }

    }

    /**
     * search node
     * @param value the value of node to be searched
     * @return the node to be searched
     */
    public Node search(int value){
        if (this.getValue() == value){
            return this;
        }else if (value < this.getValue()){
            if (this.getLeft() != null){
                return this.getLeft().search(value);
            }else {
                return null;
            }
        }else {
            if (this.getRight() != null){
                return this.getRight().search(value);
            }else {
                return null;
            }
        }
    }

    /**
     * search parent node
     * @param value value
     * @return parent node
     */
    public Node searchParent(int value){
        boolean existed = (null != this.getLeft() && this.getLeft().getValue() == value)
                || (null != this.getRight() && this.getRight().getValue() == value);
        if (existed){
            return this;
        }else if (null != this.getLeft() && value < this.getLeft().getValue()){
            return this.getLeft().searchParent(value);
        }else if (null != this.getRight() && value >= this.getRight().getValue()){
            return this.getRight().searchParent(value);
        }else {
            return null;
        }
    }

    /**
     * 判断是否是叶子节点
     * @return 叶子节点返回true，非叶子节点返回false
     */
    public boolean isLeafNode(){
        return this.getLeft() == null && this.getRight() == null;
    }

    /**
     * 获取最大的节点
     * @return 返回最大节点
     */
    public Node getMaxNode(){
        Node temp = this;
        while (temp.getRight() != null){
            temp = temp.getRight();
        }
        return temp;
    }

    /**
     * 左旋
     */
    public void leftRotate(){
        /*
         * @Date: 2021/3/30 12:54 上午
         * Step 1: 以当前根节点值为值创建新节点
         */
        Node newNode = new Node(value);
        /*
         * @Date: 2021/3/30 12:55 上午
         * Step 2: 把新节点的左子树设置为当前节点的左子树
         */
        newNode.setLeft(this.getLeft());
        /*
         * @Date: 2021/3/30 12:56 上午
         * Step 3: 把新节点的右子树设置为当前节点的右子树的左子树
         */
        newNode.setRight(this.getRight().getLeft());
        /*
         * @Date: 2021/3/30 12:57 上午
         * Step 4: 把当前节点的值替换为当前节点的右子树的值
         */
        this.setValue(this.getRight().getValue());
        /*
         * @Date: 2021/3/30 12:57 上午
         * Step 5: 把当前节点的右子树设置为当前右子树的右子树
         */
        this.setRight(this.getRight().getRight());
        /*
         * @Date: 2021/3/30 12:59 上午
         * Step 6: 把当前节点的左子树设置为新节点
         */
        this.setLeft(newNode);
    }

    public void rightRotate(){
        Node newNode = new Node(value);
        newNode.setRight(this.getRight());
        newNode.setLeft(this.getLeft().getRight());
        this.setValue(this.getLeft().getValue());
        this.setLeft(this.getLeft().getLeft());
        this.setRight(newNode);
    }

    /**
     * infixOrder
     */
    public void infixOrder(){

        if (this.getLeft() != null){
            this.getLeft().infixOrder();
        }
        System.out.println(this);
        if (this.getRight() != null){
            this.getRight().infixOrder();
        }
    }

    /**
     *
     * @return 返回以该节点为根节点的树的高度
     */
    public int height(){
        return Math.max(left == null ? 0 : left.height(),
                right == null ? 0 : right.height()) +1;
    }

    /**
     *
     * @return 返回左子树的高度
     */
    public int leftHeight(){
        if (left == null){
            return 0;
        }
        return left.height();
    }

    /**
     *
     * @return 返回右子树的高度
     */
    public int rightHeight(){
        if (right == null){
            return 0;
        }
        return right.height();
    }

    public Node(int value) {
        this.value = value;
    }

    public Node() {
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}
